
int Max(int x, int y) {
    return (x > y) ? x : y;
}

bool IsCompatible(Activities a, int *room, int i, int k) {
    /* i是否可以被放入第k个教室 */
    int j;
    bool ret;

    ret = false;
    for (j = i - 1; j >= 0; j--) {
        if (room[j] == k) { /* 教室k中最后开始的活动是j */
            if (a[j].finish <= a[i].start) {
                ret = true;
            }
            break;
        }
    }
    return ret;
}

int ActivityScheduling(Activities a, int n) {
    /* n个活动按照 a[i].start的非递减序存放 */
    int *m, *room, i, k;

    m = (int *)malloc(sizeof(int) * (n + 1));
    room = (int *)malloc(sizeof(int) * (n + 1));
    m[0] = 1; /* 第0个活动占用1个教室 */
    room[0] = 1; /* 第0个活动占用1号教室 */
    for (i = 1; i <= n; i++) {
        /* 找到i可以排入的第一个教室的序号 */
        for (k = 1; k <= m[i - 1]; k++) {
            if (IsCompatible(a, room, i,
            k) == true) { /* 若i可以被放入第k个教室 */
                break;
            }
        }
        /* 如果i放不进任何教室，则k= m[i-1]+1 */
        m[i] = Max(m[i - 1], k);
        room[i] = k; /* 将i排入教室k */
    }
    return m[n];
}

/* 更快的解决方案 */
//int ActivityScheduling(Activities a, int n)
//{ /* n个活动按照 a[i].start的非递减序存放 */
// int *m, *room, i, k;
//
// m = (int *)malloc(sizeof(int) * (n+1));
// room = (int *)malloc(sizeof(int) * (n+1));
// m[0] = 1;    /* 第0个活动占用1个教室 */
// room[1] = 0; /* 1号教室的最迟结束时间为0 */
// for (i=1; i<=n; i++) {
// /* 找到i可以排入的第一个教室的序号 */
// for (k=1; k<=m[i-1]; k++) {
// if (room[k] <= a[i].start) { /* 若i可以被放入第k个教室 */
// break;
// }
// }
// /* 如果i放不进任何教室，则k= m[i-1]+1 */
// m[i] = Max(m[i-1], k);
// room[k] = a[i].finish; /* 将i排入教室k */
// }
// return m[n];
//}